Distributed systems are frequently used to store and perform operations on large data sets. However, the scalability of this solution is limited because the performance of distributed data processing systems is often bottlenecked by communication latency. When a data set is distributed across multiple machines, communication latency is caused by the time delay to move data across different machines. For example, when a set of computations is performed on data that must be retrieved from a different machine, a thread or process of the local machine must wait for the data to be retrieved before finishing the set of computations. When the set of computations can be performed quickly, the wait time becomes a limiting factor. For example, if the local machine performs computations on an amount of remotely-stored data that is small, and the computation time scales relative to the size of the data, then the computation time will be small relative to the communication time since the communication time includes latency that does not decrease with the size of the data.
Context switching is one technique to address communication latency. Context switching is the process of storing the context, or state, of a process or thread so that execution can be resumed from the same point at a later time. In distributed data processing systems, when a plurality of concurrent tasks is processed, context switching is implemented as follows: when a thread handles a task that requires a remote data access, the task initiates a remote access request and the task is suspended. Meanwhile, the thread is free to perform other tasks, freeing up the computational resource. The execution of the suspended task is resumed when the remote data access is complete. This context switching technique is typically implemented with a ready task queue and a suspended task queue. One or more worker threads select tasks to execute from the ready task queue. Suspended tasks that require remote data access are placed into the suspended task queue. When a remote data access is complete, the task is moved back to the ready task queue so that worker threads can resume execution.
The context switching mechanism described above is effective at hiding communication latency when the number of remote data accesses and concurrent tasks is small. However, the ready task queue and the suspended task queue become a performance bottleneck under certain conditions, such as when the number of remote data accesses is large, the number of concurrent tasks is large, and/or the data size of each remote data access is small. These conditions tend to occur for distributed graph processing on large graph data sets.
Graph-based modeling of data is a powerful tool for analyzing and discovering relationships within a data set. When the dataset is larger than the main memory of a single machine, distributed graph processing is particularly useful. Many graph operations are easily parallelizable due to the characteristics of graph-based models. However, communication latency reduces the scalability of distributed graph processing because graph analysis workloads typically involve a massive number of concurrent tasks that require many remote data accesses, including many remote accesses of a small amount of data. Often, the amount of the available computation of the distributed system is not utilized because communication latency acts as a bottleneck.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.